1. Technical Field
The invention is a high speed digital error diffusion process which increases the speed at which a gray scale image can be converted to a binary or bi-tonal image with error diffusion.
2. Background Art
Many image reproduction devices, such as many types of printers for example, can produce only binary (bi-tonal) images consisting typically of uniform black dots on a white background. In order for such a device to reproduce a gray scale or continuous tone image (in which each pixel can assume any value within a range), the gray scale image must be converted to a binary image, which is then transmitted to the reproduction device. In the simplest conventional approach for accomplishing this, each gray scale pixel is compared with a print decision threshold to determine whether or not to print a black dot for the corresponding binary image pixel. If the gray scale pixel value exceeds the threshold, a black dot is printed in the corresponding location in the binary image. A more sophisticated approach is digital half-toning, in which the gray scale pixels are converted to arrays of dispersed uniform-sized dots in accordance with the respective gray scale values.
Binarization of the gray scale image introduces objectionable noise into the binarized image. Various techniques for reducing such noise are discussed in U.S. Pat. No. 4,339,774 to Temple. One such technique is ordered dither, which varies the print decision threshold against which the gray scale value of each pixel in the gray scale image is compared. Such dithering of the threshold is performed in accordance with a repetitive spatial pattern so as to mask the binarization noise. Another technique is error diffusion, in which the error between the gray scale pixel value and the print value of the corresponding binary image pixel is distributed among neighboring pixels. This is done by adding a fraction of the error to each neighboring pixel in the gray scale image to generate a "diffused" gray scale pixel value. The diffused pixel value is then compared with the threshold to determine the binary pixel value. Various combinations of some or all of the foregoing techniques may be made. For example, ordered dither and error diffusion may be employed with or without halftoning in an image binarization process. The present invention is related to improving the error diffusion process.
The error diffusion process is illustrated in FIG. 1a. In an array 10 of image pixels, the difference between the gray scale pixel value of a given image pixel 12 and the corresponding pixel value in the binary image is the error e. In a binarization process which proceeds through the array 10 row-by-row and left to right pixel-by-pixel, the error e is distributed (diffused) among the nearest neighboring pixels which have yet to be processed. As indicated in FIG. 1a, the three nearest neighboring pixels are altered by adding e/4 to their respective gray scale values while the remaining two neighboring pixels are altered by adding e/8 to their respective gray scale values before they are compared with a print decision threshold. Since this must be done for all pixels in the image array 10, it follows that the diffused pixel value for a given pixel P is computed as shown in FIG. 1b. The new or diffused gray scale pixel value of the pixel P in FIG. 1b is computed by adding 1/4 of the errors from each of the three nearest neighbor pixels and 1/8 of the errors from the remaining two neighbor pixels to the original gray scale value of P. The diffused pixel value is called P.sub.dif.
The foregoing error diffusion process may be defined by reference to FIGS. 2a and 2b. FIG. 2a illustrates the pixel P and its five nearest neighbors P.sub.1, P.sub.2, P.sub.3, P.sub.4, P.sub.5 which were processed before P in preceding cycles of the error diffusion process. FIG. 2b illustrates the corresponding errors e.sub.1, e.sub.2, e.sub.3, e.sub.4, e.sub.5 and E for these same pixels. The diffused error at the current pixel P is defined as: EQU ED =(1/8)e.sub.1 +(1/4)e.sub.2 +(1/4)e.sub.3 +(1/8)e.sub.4 +(1/4)e.sub.5 (1)
in which the sum of the coefficients is unity.
The diffused pixel value at the current pixel P is defined as: EQU P.sub.dif =P +ED. (2)
The print value (either black or white) selected for the current pixel P will be referred to as PV. If a black dot is printed, then PV is the maximum n-bit value. Otherwise, PV is zero. The error E at the current pixel is computed as follows: EQU E =P.sub.dif -PV. (3)
The dither threshold (or print decision threshold) will be referred to as D. The print value PV for the current pixel is the maximum n-bit number (black) if P.sub.dif .gtoreq.D and is zero (white) otherwise. In two's complement arithmetic the most significant bit of a word is its sign bit, and PV may be defined as follows: EQU PV =[M.S.B. of (P.sub.dif -D].sup.-1 .times.[maximum n-bit value], (4)
where M.S.B denotes most significant bit--the sign bit--and the superscript -1 denotes an inversion of the bit.
Equations (1) through (4) constitute one cycle of the error diffusion process. The current pixel error E of equation (3) becomes the previous pixel error e.sub.5 of the next cycle.
One variation of the foregoing process disclosed in U.S. Pat. No. 4,891,710 to Nakazato is to quantize the error E by dropping the n least significant bits of E in the current cycle, and to apportion these bits among the errors of other pixels in subsequent cycles.
The foregoing computations are time-consuming and must be performed once in each cycle of the error diffusion process. In particular, the computations of a given cycle cannot begin until the previous pixel error e.sub.5 has been computed. The computation of the previous pixel error e.sub.5 cannot begin until the previous print value is determined upon the completion of the previous cycle. Thus, the error diffusion process cycle cannot proceed any faster than the time required to compute the previous pixel error e.sub.5.
Therefore, there is a need for a way of reducing the amount of time required to perform the calculations of equations (1) through (4) in each cycle of the error diffusion process. It has not seemed possible to reduce the time required to perform these calculations, since none of the steps can be omitted without loosing the desired effects of error diffusion. Moreover, the time required to perform the calculations in a given integrated circuit technology is a fixed quantity.
Accordingly, it is the principal object of the invention to reduce the amount of time required to perform each cycle of the error diffusion process by modifying the error diffusion computations without affecting the error diffusion process or losing any of its effects or benefits.
It is a related object of the invention to take advantage of the iterative nature of the calculations of the error diffusion process by using the results of some of the calculations in one cycle as the interim results of related calculations in the next cycle, whereby no time is spent computing the interim results in the next cycle. More specifically, it is an object of the invention to begin a portion of the computation of the previous pixel error e.sub.5 of the current cycle before the end of the previous cycle and complete the rest of the computation during the current cycle.
It is another related object of the invention is to take advantage of the following precepts of the invention which apply to all but the least significant bit of the diffused pixel value P.sub.dif : (A) in two's complement arithmetic, the n least significant bits (LSB's) of the diffused pixel value P.sub.dif computed in the step of equation (2) are the same as the n LSB's of the previous pixel error e.sub.5 computed in the later step of equation (3); and, (B) only the sign bit or MSB of the previous pixel error e.sub.5 cannot be determined from the diffused pixel value P.sub.dif.
It is a further related object of the invention to use a portion of the diffused pixel value P.sub.dif computed in a previous cycle as the two's complement absolute value--the n least significant bits or LSB's--of the previous pixel error e.sub.5 of the current cycle, thus obviating the need to calculate these bits during the next cycle.
It is a still further object of the invention to use the most significant bits (MSB's) of P.sub.dif of the previous cycle to immediately determine the sign bit or MSB of the previous pixel error e.sub.5 of the current cycle.